/*
 *https://leetcode.cn/problems/time-needed-to-inform-all-employees/description/
 *1376. 通知所有员工所需的时间
 *medium 吴朝泽 2024.10.24
 *DFS深度优先搜索
*/

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        // 创建一个图，存储每个经理管理的员工
        vector<vector<int>> g(n);
        for (int i = 0; i < n; ++i) {
            // 如果经理的ID有效（即不为-1），则将员工添加到经理的列表中
            if (manager[i] >= 0) {
                g[manager[i]].push_back(i);
            }
        }
        
        // 深度优先搜索函数，用于计算从当前经理开始的最大信息传递时间
        function<int(int)> dfs = [&](int i) -> int {
            int ans = 0;   // 初始化当前节点的最大传递时间
            for (int j : g[i]) { // 遍历当前经理的所有下属
                // 递归计算下属的信息传递时间，并更新最大时间
                ans = max(ans, dfs(j) + informTime[i]);
            }
            return ans; // 返回当前节点的最大信息传递时间
        };
        
        return dfs(headID);
    }
};

